package slidingwindow.leetcode_239_slidingwindow;

import java.util.Deque;
import java.util.LinkedList;

public class DequeSolution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(nums == null || len == 0 || k == 0 || k > len){
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[len - k + 1];
        int index = 0;
        for(int i = 0; i < len; i++){
            //队列中的元素大小严格递减
            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            /*
                当 队列中的元素个数 与 窗口大小相等时，插入下一个元素时，要删除队头元素
             */
            if(deque.peekFirst() == i - k){
                deque.pollFirst();
            }
            //当已经形成了窗口时，收集结果
            if(i >= k - 1){
                res[index++] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}
/*
    输入: nums = [1,3,-1,-3,5,3,2,1], 和 k = 3
    输出: [3,3,5,5,6,7]

    利用一个双端队列，形成一个K大小的窗口，队列中保存数组中元素的对应下标，并且队列中的元素从左到右都是严格递减的。
        开始时，窗口值为0，利用L表示窗口的左边界，R表示窗口的右边界。 L = R = 0;
        队列为空

        过程
        i = 0, nums[0] = 1, 队列为空，直接加入，deque = {1}，窗口值为1
        i = 1, nums[1] = 3, 不满足严格递减条件，弹出队列中的元素，直至满足条件，deque = {3}, 窗口值为2
        i = 2, nums[2] = -1，满足条件，deque = {3, -1}, 窗口值为3，队头元素为最大值 收集 res = {3}，维持大小为3的窗口
        i = 3, nums[3] = -3, 满足条件，deque = {3, -1, -3}, 收集最大值 res = {3,3}
        i = 4, nums[4] = 5, 弹出队列中的元素，直至满足条件, deque = {5} , 收集最大值 res = {3,3,5}
        i = 5, nums[5] = 3, 满足条件，deque = {5,3}，收集最大值 res = {3,3,5,5}
        i = 6, nums[6] = 2, 满足条件，deque = {5,3,2}，收集最大值 res ={3,3,5,5,5}
        i = 7, nums[7] = 1, 满足条件
            此时队列大小和窗口值相等，插入新元素时要删除队头的过期元素，deque = {3,2,1}，收集最大值res={3,3,5,5,5,3}
 */
